package com.johann.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class T653_TwoSumIV {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Solution {
        public boolean findTarget(TreeNode root, int k) {
            // 二叉搜索树
            if(root==null) return false;
            // 中序遍历后将val值存到ArrayList中
            List<Integer> arr= inorder(root);
            Integer[] nums = arr.toArray(new Integer[arr.size()]);
            // k - root.val < root.val 左边找，下一级递归
            HashMap<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if(map.containsKey(k-nums[i])){
                    return true;
                }
                map.put(nums[i],i);
            }
            return false;
        }

        public List<Integer> inorder(TreeNode root){
            List<Integer> temp = new ArrayList<>();
            inorder(root,temp);
            return temp;
        }
        // 中序遍历
        public void inorder(TreeNode root,List list){
            if (root==null) {
                return ;
            }
            inorder(root.left,list);
            list.add(root.val);
            inorder(root.right,list);
        }
    }

    static class Solution2{
        // 二叉搜索树 的节点值 无重复
        HashSet<Integer> set = new HashSet<>();
        public boolean findTarget(TreeNode root, int k) {
            if(root==null) return false;
            if (set.contains(k- root.val)) {
                return true;
            }
            set.add(root.val);
            return findTarget(root.left,k)||findTarget(root.right,k);
        }
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(5);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(6);
        TreeNode t4 = new TreeNode(2);
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(7);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = null;
        t3.right = t6;
        System.out.println(new Solution().findTarget(t1, 9));
        System.out.println(new Solution2().findTarget(t1, 9));
    }
}
